
#include<stdio.h>
//插入排序--》希尔排序
//升序
void ShellSort(int* arr, int size) {
	int gap = 3;
	while (1) {
		for (int i = gap; i < size; i += gap) {
			int end = i - gap;
			int key = arr[i];
			while (end >= 0 && arr[end] > key) {
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = key;
		}
		if (1 == gap)
			break;
		gap = gap / 3 + 1;
	}
	return;
}

void ShellPrint(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, size);
	ShellPrint(arr, size);
	return 0;
